今天刷题的时候遇到了一道中国剩余定理的题,当年在网络安全这门课上学过这个算法,但是到现在只记得这个名字了,就回去翻课件回顾了一下,结果发现了很多知识点,就在这整理一下.

---

乘法逆元

乘法逆元这个概念最初是在离散数学中引入的, 而在离散数学中提到的是范围更广泛的逆元. 是在代数系统里面提到的这个概念 定义如下

令e为S中关于某二元运算的单位元.对于x∈S,如果存在yl（或yr）∈S使得(yl)x=e（或x(yr)=e）,则称yl(或yr)是x的左逆元(或右逆元)。若y∈S既是x的左逆元又是x的右逆元,则称y为x的逆元。如果x的逆元存在,就称x是可逆的.

在这里,二元运算就是模p乘法,p就是整个集合的范围.在这里,如果w是Zp中的某个数,我们求w的乘法逆元,这里有一条定理.

Zp中的任一整数w有乘法逆元当且仅当w和p互素

这里可以简单证明一下必要性,w和p互素,我们可以用w乘Zp中的所有元素,得到的剩余类是Zp中所有元素的另一种排列. 以上这句话可以用反证法来证明 假设乘完得到的剩余类并不是Zp的另一种排列,说明得到的剩余类中必定有两个相同的数.设为m,则:

k1*w = s1*p + m
k2*w = s2*p + m

所以

(k1-k2)*w = (s1-s2)*p

因为w和p互素 (k1-k2)应该等于p,而k1,k2都小于p,得到了矛盾.得证.

现在知道了,如果求乘法逆元,要求这个数应该和基数p互素,下面看怎么求乘法逆元.

Euclid算法

Euclid的扩展算法可以用来求乘法逆元.先来看一下基本的Euclid算法. 整个算法写起来很简单

gcd(a,b) = gcd(b,a%b)

证明起来也很简单,具体看<密码编码学与网络安全>P74 这里说一下扩展的Euclid用于求乘法逆元. 就是假设 gcd(a,b) = d, d 能写成 a和 b的组合形式 d = xa + yb 这样,当x,y互素的时候,明显d == 1,可以得到x是a的乘法逆元,y是b的乘法逆元. 具体x和y的推导计算可见<密码编码学与网络安全>p81

中国剩余定理

这个才是重点,首先中国剩余定理(Chinese Remainder Theorem)的意义是说明某一范围内的整数可通过它对两两互素的整数取模所得的余数来重构.

具体证明如下